

class LinkedQueue:
    """
    FIFO queue implementation using a singly linked list.
    """
    class _Node:
        """Singly linked node"""
        __slots__ = '_element', '_next'

        def __init__(self, element, next):
            self._element = element
            self._next = next

    def __init__(self):
        """Create an empty singly linked queue"""
        self._head: LinkedQueue._Node = None
        self._tail: LinkedQueue._Node = None
        self._size = 0

    def __len__(self):
        return self._size

    def __str__(self):
        data = []
        walk_node = self._head
        while walk_node:
            data.append(walk_node._element)
            walk_node = walk_node._next
        return str(data)

    def is_empty(self):
        return self._size == 0

    def first(self):
        """
        Return the element at the front of the queue
        :return:
        """
        if self.is_empty():
            raise Exception("queue is empty")
        return self._head._element

    def tail(self):
        """
        Return the element at the tail of the queue
        :return:
        """
        if self.is_empty():
            raise Exception("queue is empty")
        return self._tail._element

    def enqueue(self, value):
        """
        Add an element to the tail of the queue
        :param value:
        :return:
        """
        new_node = self._Node(value, None)
        if self.is_empty():
            self._head = new_node
        else:
            self._tail._next = new_node
        self._tail = new_node
        self._size += 1

    def dequeue(self):
        """
        Remove and return the first element of the queue.
        :return:
        """
        if self.is_empty():
            raise Exception("queue is empty")
        value = self._head._element
        self._head = self._head._next
        self._size -= 1
        if self.is_empty():
            self._tail = None
        return value

    def rotate(self):
        """Rotate front element to the back of the queue"""
        if not self.is_empty():
            self._tail._next = self._head

        self._head = self._head._next
        self._tail = self._tail._next
        self._tail._next = None
